Many organizations, including businesses, governments and educational institutions, utilize computer networks so that employees and others may share and exchange information and/or resources. A computer network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that "sources" (i.e., transmits) or "sinks" (i.e., receives) data frames over the communications media. A common type of computer network is a local area network ("LAN") which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network ("WAN") or subnet that may span an entire country or continent.
One or more intermediate devices is often used to couple LANs together and allow the corresponding entities to exchange information. For example, a switch may be utilized to provide a "switching" function for transferring information, such as data frames, among entities of a computer network. Typically, the switch is a computer and includes a plurality of ports that couple the switch to the other entities. The switching function includes receiving data at a source port from an entity and transferring that data to at least one destination port for receipt by another entity.
Another network device is referred to as a router. A router is typically used to interconnect LANs executing different LAN standards and/or to provide higher network functionality, such as efficient message routing. To perform these tasks, a router, which is also often a computer, typically examines and may modify the destination address and source address of all packets passing through the router. Routers typically operate at the network layer of the protocol stack, such as the Internet Protocol of the Transmission Control Protocol/Internet Protocol ("TCP/IP") reference model. If the LAN standards associated with the source entity and the destination entity are dissimilar (e.g., Ethernet versus Token Ring), the router may alter the format of the packet so that it conforms with the standard corresponding to the destination entity.
FIG. 1 illustrates a conventional computer network 100 comprising a plurality of local area networks (LANs) 101-108 that are interconnected by a plurality of switches 111-118 and routers 121-123. More specifically, each LAN 101-108 is preferably coupled to at least one port 124 of switches 111-118. One or more entities (not shown) for sourcing or sinking data frames are preferably coupled to each LAN 101-108. The switches 111-118 and routers 121-123 are interconnected by a series of links 126, such as point-to-point links. Links 126 also couple to ports 124 of the switches 111-118 and routers 121-123. Each switch 111-118 and router 121-123, moreover, may individually identify its ports, e.g., by numbers one, two, three, etc. Accordingly, each switch 111-118 and router 121-123 may associate a given port with the particular LAN, switch or router coupled thereto. For example, switch 111 may associate its port number one with LAN 101, port numbers two and three with router 121, port number four with switch 112 and port number five with LAN 102.
The network 100 may also include devices for providing services to the entities. For example, network 100 preferably includes a file server 128. The file server 128 may be connected to router 121 by two links 126. Separate ports 124 (e.g., port numbers one and two) at the file server 128 may be associated with each of the links 126. Thus, data frames may be forwarded by router 121 over either link 126 for receipt by the file server 128.
Like most computer networks, network 100 includes redundant communications paths so that a failure of any given link does not isolate any portion of the network 100. For example, switch 111 is connected to router 121 by two links 126. Thus, in the event one of these links 126 fails, communication between switch 111 and router 121 may continue through the other link 126. Similarly, routers 122 and 123 are interconnected by multiple links 126 as are router 121 and the file server 128. The existence of redundant links, however, can introduce significant problems in the network 100.
For example, file server 128 may have a different address associated with each of its ports 124, i.e., port numbers one and two. These addresses are used by entities on LANs 101-108 when communicating with the file server 128, e.g., requesting services. The entities, however, may not be aware of both addresses. That is, entities located on LANs 103 and 104 may only be aware of the address of the file server 128 that corresponds to its port number one whereas, entities on LANs 101 and 102 may only be aware of the file server 128 through its address corresponding to port number two. Accordingly, if one of the links 126 that connects the file server 128 with router 121 were to fail, certain entities may be unable to access the file server 128. For example, if the link 126 associated with port number one of the file server 128 were to fail, entities on LANs 103 and 104 would no longer be able to communicate with the file server 128, even though the adjacent link between the file server 128 and router 121 (i.e., the link coupled to port number two of the file server 128) is still functioning. That is, messages addressed to port number one of the file server 128 (which is the only address known by entities on LANs 103 and 104) cannot be delivered by router 121, due to the failure of the link corresponding to that port.
One solution to this problem is for router 121 to inform entities on LANs 103 and 104 to address the file server 128 at its port number two following a link failure. This requires router 121 to constantly monitor the availability of both links 126 coupled to the file server 128. In addition, the router 121 must transmit access messages to each entity on LANs 103 and 104 in the event of a failure of the link. This activity consumes substantial system resources. In addition, some amount of time is required for the access messages from router 121 to reach the entities on LANs 103 and 104, during which time messages addressed to the file server 128 via port number one may still be lost.
The existence of redundant links may also cause the formation of circuitous paths or "loops" within the network 100. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, as a frame travels along a loop, some devices, such as switches 111-118, may become so "confused" as to the location of the entity sourcing the frame as to actually proliferate these "looping" data frames. That is, switches 111-118 may create additional copies of these looping frames. The resulting traffic may effectively "shut-down" the network 100. Intermediate devices, such as routers 121-123, that operate at higher hierarchical layers (e.g., the network layer) within the protocol stack, deliver data frames and learn the addresses of entities on the network differently than switches 111-118, such that routers are generally not susceptible to sustained looping problems.
To avoid the formation of loops, intermediate devices, such as switches, within each segment of the network execute what is known as a spanning tree algorithm. This algorithm effectively "severs" the redundant links within the network segments. More specifically, switches exchange special messages called bridge protocol data unit (BPDU) frames that allow them to calculate a spanning tree, which is a subset of the network segment that is loop-free (i.e., a tree) and yet connects every pair of LANs within the segment (i.e., the tree is spanning). The BPDU frames contain sufficient information, such as the relative cost of transmitting data frames over the links and interconnecting LANs, for the switches to discover a loop-free tree. Using this information, the switches calculate the tree in accordance with the algorithm and typically elect to sever or block all but one of the redundant links or communications paths. The spanning tree algorithm and the BPDU messages are well-known and documented (see IEEE Standard 802.1D).
Switches place each port corresponding to a severed link 126 in a blocking mode. When a port is in the blocking mode, the associated switches will not forward any data frames to or from that port. The ports corresponding to the remaining communications paths or links are placed in a forwarding mode so that data frames may be forwarded to and from those ports and thus onto the corresponding paths or links.
In general, switches learn the locations of entities by examining the source addresses of received data frames and maintain this information in a filtering database. Pursuant to the spanning tree protocol, a change in network topology (e.g., the failure or recovery of a link) typically causes the switches to time out the information in the filtering database. As a result, after the spanning tree determines which ports should be placed in the blocking or forwarding modes under the new network topology, data frames must be initially flooded while the bridges re-learn the locations of entities. Significant communications bandwidth and time are thus often consumed during reconfigurations. Higher layer protocols, such as file transfer applications or network log ons, may similarly time out while the spanning tree protocol attempts to stabilize under the new topology resulting in further inefficiencies.
As shown in FIG. 1, four network segments exist, including: (1) switches 111 and 112; (2) 113; (3) 114-116; and (4) 117 and 118 and thus an independent spanning tree algorithm runs in each segment. A loop, moreover, exits in the segment comprising switches 111 and 112 by virtue of the connections through LAN 102 and link 126 extending between the two switches. Execution of the spanning tree algorithm in this segment may result in switch 111 placing its port number five in the blocking state (as illustrated by the `X`), thereby avoiding the loop. Switch 111 will not forward any data frames arriving on port number five or forward any data frames through that port. Loops also exist in the segments comprising switches 114 and 115 and 117 and 118. Execution of the spanning tree algorithms in these segments may result in switch 114 placing its port two in the blocking mode and switches 115 and 118 placing their ports two and one, respectively, in the blocking mode.
Since the spanning tree algorithms essentially block all but one of the redundant links between two looped devices, all of the data frames exchanged between those devices must be carried on the single link or path corresponding to the one port placed in the forwarding mode. No data may be exchanged over the links or paths associated with blocked ports. Thus, despite the existence of multiple communications paths, all but one of the paths or links remain idle. Accordingly, the spanning tree algorithm results in a significant waste of system resources.
A mitigating solution to this problem of waste is for a network administrator to manually identify and combine the redundant links connecting two looped devices as described in the EtherSwitch Pro16 Installation and User's Guide dated May 1995 from Cisco Systems, Inc. More specifically, the administrator may issue requests for status messages to the intermediate devices. By reviewing the information received from the intermediate devices, the administrator may be able to identify the existence of redundant links or paths between two intermediate devices. Once identified, the administrator may issue configuration messages instructing the intermediate devices to combine the redundant physical links. Thereafter, upon execution of the spanning tree algorithm, these network devices will treat the redundant links as a single link. That is, the spanning tree algorithm will not detect multiple links forming a loop. The system administrator may also configure these intermediate devices to forward frames across each physical link.
This solution is disadvantageous for several reasons. First, it requires substantial involvement of the network administrator and is thus time-consuming and expensive to implement. In particular, the combination of links must be reviewed by the network administrator every time the network topology changes (e.g., a cable is added/removed, a device is added or moved, a device fails or recovers, etc.). Second, the solution is highly error prone. That is, the administrator may incorrectly identify a loop, may issue configuration messages to the wrong devices or ports, etc. These errors may generate serious network problems that may be difficult to detect.